from typing import List


class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        # dp[i][j]代表：nums1[i]为起点倒排 与 nums2[j]为起点倒排 的公共部分长度
        dp = [[0] * len(nums2) for _ in range(0, len(nums1))]
        res = 0
        # dp初始化
        if nums2[0] == nums1[0]:
            dp[0][0] = 1
            res = max(dp[0][0], res)
        for i in range(1, len(nums1)):
            if nums2[0] == nums1[i]:
                dp[i][0] = 1
                res = max(dp[i][0], res)
        for j in range(1, len(nums2)):
            if nums2[j] == nums1[0]:
                dp[0][j] = 1
                res = max(dp[0][j], res)
        # dp状态转移
        for i in range(1, len(nums1)):
            for j in range(1, len(nums2)):
                if nums1[i] == nums2[j]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    res = max(res, dp[i][j])
        return res


if __name__ == "__main__":
    solution = Solution()
    res = solution.findLength(nums1=[0, 1, 1, 1, 1], nums2=[1, 0, 1, 0, 1])
    print(res)
